import java.util.ArrayList;
import java.util.Arrays;

public class Wu_5_17 {
    public static void main(String[] args) {
//        //call fib
//        int n=new Wu_5_17().fib(3,4);
//        System.out.println(n);
//
//        // call paths
        int[][] grid =new int[3][4];
        int m=new Wu_5_17().paths(grid);
        //System.out.println(m);
        //System.out.println(new Wu_5_17().paths2(grid));
        //here are some obstacles,the obstacle is marked by -1
        grid[1][1]=-1;
        grid[0][2]=-1;
        //System.out.println(new Wu_5_17().paths(grid));
        //System.out.println(new Wu_5_17().paths2(grid));

//        // call rodCutting
        int [] rod=new int[]{0,1,5,8,9,10,17,17,20,24,30};
//        System.out.println(new Wu_5_17().rodCutting(rod,8));
//       System.out.println(new Wu_5_17().rodCutting2(rod, 8));
//
//        //call rodCut
//        System.out.println(new Wu_5_17().rodCut(rod,8));
        System.out.println(new Wu_5_17().rodCut(rod, 8));

//
//        //call dungeonGame
        int[][] grids=new  int[][]{{-3,1,-4},{4,-8,3},{-5,6,-7}};
//        System.out.println(new Wu_5_17().dungeonGame(grids));
        System.out.println(new Wu_5_17().fib(4,3));
        System.out.println(new Wu_5_17().dungeonGame(grids));
    }
    // return the minimum HP
    int dungeonGame(int [][] grid){
        if(grid==null || grid.length==0 || grid[0].length==0) return 0;
        int m= grid.length;
        int n=grid[0].length;
        grid[0][n-1]=Math.max(1,1-grid[0][n-1]);
        //the last column
        for(int i=1;i<m;i++){
            grid[i][n-1]=Math.max(1,grid[i-1][n-1]-grid[i][n-1]);
        }
        //the last row
        for(int j=n-2;j>=0;j--){
            grid[0][j]=Math.max(1,grid[0][j+1]-grid[0][j]);
        }
        // the middle row and column
        for (int i=1;i<m;i++){
            for(int j=n-2;j>=0;j--){
                int right=Math.max(1,grid[i][j+1]-grid[i][j]);
                int up=Math.max(1,grid[i-1][j]-grid[i][j]);
                grid[i][j]=Math.min(right,up);
            }
        }
        return grid[m-1][0];

    }

    // each time can climb (int step) steps to reach the top (int n)
    int fib(int n,int step) {
        if (n < step) {
            if (n == 0 || n == 1)
                return 1;
             return fib(n,n);
        }
        int sum=0;
        for(int i=1;i<=step;i++)
            sum+=fib(n-i,step);
        return sum;
    }
    // return the sum of all paths
    int paths(int[][] grid){
        for(int i=1;i< grid.length;i++)
            if(grid[i][0]==-1){
                for(;i< grid.length;i++)
                    grid[i][0]=0;
            }else grid[i][0]=1;

        for(int j=1;j<grid[0].length;j++){
            if(grid[0][j]==-1){
                for(;j<grid[0].length;j++)
                    grid[0][j]=0;
            }else grid[0][j]=1;
        }

        for(int i=1;i< grid.length;i++)
            for(int j=1;j<grid[0].length;j++) {
                if(grid[i][j]==-1)
                    grid[i][j]=0;
                else
                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
            }
        return grid[grid.length-1][grid[0].length-1];
    }

    //cut strips to get the max profit
    //bottom up (circulation)
    int rodCutting(int[] rod,int length){
        int[] profits=new int[length+1]; // +1 let the subscript adapt to the real length
        // dynamic programing
        for(int i=1;i<=length;i++){
            int [] r=new int[i/2+1]; // the method of cutting rod
            for(int j=0;j<r.length;j++) {
                r[j] = rod[j] + rod[i - j];// j=0,not cut
            }
            //sort
            quicksort(r,0,r.length-1);
            profits[i]=r[r.length-1];
            rod[i]=profits[i]; // update rod to get the maximum profit
        }
        return profits[length];
    }
    //top down (recursion)
    int rodCut(int[] rod, int p){
        if(p<=1) return rod[p];
        int q=Integer.MIN_VALUE;
        for(int i=1;i<=p;i++)
            q=Math.max(q,rod[i]+rodCut(rod,p-i));
        return q;

    }

    void quicksort(int [] array,int low,int high){
        if(low>=high) return;
        int i=low ,j=high;
        //select a base
        int base =array[low];
        while(i<j){
            while(array[j]>=base && i<j)
                j--;
            while(array[i]<=base && i<j)
                i++;
            swap(array,i,j);
        }
        swap(array,low,j);
        quicksort(array,low,j-1);
        quicksort(array,j+1,high);
    }
    void swap(int[]array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}
